// 单词拆分

package Leetcode;

import java.util.ArrayList;
import java.util.List;

class Soltuion_139_1 {

    public boolean result = false;

    public boolean wordBreak(String s, List<String> wordDict) {
        backTrace(s, 0, wordDict);
        return result;
    }

    public void backTrace(String s, int start, List<String> wordDict) {
        if (start == s.length())
            result = true;

        // 超出时间限制
        // for (int i = start + 1; i <= s.length(); i++) {
        // String sub = s.substring(start, i);
        // if (wordDict.contains(sub))
        // backTrace(s, i, wordDict);
        // }
        // 超出时间限制
        // for (String string : wordDict) {
        // int length = string.length();
        // if (start + length > s.length())
        // continue;
        // String substring = s.substring(start, start + length);
        // if (string.equals(substring))
        // backTrace(s, start + length, wordDict);
        // }

    }

    public static void main(String[] args) {
        List<String> list = new ArrayList<>();
        list.add(new String("abc"));
        list.add(new String("bcd"));
        list.add(new String("cde"));
        System.out.println(list.contains("abc"));
        // String s = "abcd";
        // for (int i = 1; i <= s.length(); i++)
        // System.out.println(s.substring(0, i));
    }
}

// 动态规划
class Soltuion_139_2 {
    public boolean wordBreak(String s, List<String> wordDict) {
        // dp[i]表示串0~i是否可以被分割
        boolean[] dp = new boolean[s.length() + 1];
        // 初始化
        dp[0] = true;
        for (int i = 1; i <= s.length(); i++) {
            for (int j = 0; j <= i; j++) {
                if (dp[j] && wordDict.contains(s.substring(j, i))) {
                    dp[i] = true;
                    continue;
                }
            }
        }
        return dp[s.length()];
    }
}